/**
 * 递归
 */
/*归的时候才开始打印，递归主要在归，倒着输出*/
public class TestDemo {
    //写一个递归方法，输入一个非负整数，返回组成它的数字之和
    /* /10 %10 */
    public static int print5(int n){
        if(n>9){
            return print5(n/10)+n%10;
        }
        return n%10;
    }
    public static void main8(String[] args) {
        System.out.println(print5(1234));
    }
    //求斐波那契数列的第 N 项
    /*非递归
    * 需要a,b,c三个变量，c = a+b
    * 变量还需进行交换*/
    public static void main7(String[] args) {
        int n = 10;
        int a = 1;
        int b = 1;
        int c = 1;
        while(n>2){
            c = a + b;
            a = b;
            b = c;
            n--;
        }
        System.out.println(c);

    }
    //求斐波那契数列的第 N 项
    /*递归：
    终止条件：n = 1,和 n = 2时，返回1
    递归公式：fib(n) = fib(n-1)+fib(n-2)
    */
    public static int fib(int n){
        if(n<=2){
            return 1;
        }else{
            return fib(n-1)+fib(n-2);
        }
    }
    public static void main6(String[] args) {
        System.out.println(fib(10));
    }
    //递归求 1 + 2 + 3 + ... + 10
    /*输入10，则求1-10的和。
    * 终止条件:n = 1
    * 递归公式：1-10的和 = 10 + 1-9的和。每次-1的值返回与前面的值相加*/
    public static int sum(int n){
        if(n == 1){
            return 1;
        }else{
            return sum(n-1)+n;
        }
    }
    public static void main5(String[] args) {
        System.out.println(sum(10));
    }
    /*需要将每位数字加起来
    * 求1234的和 = 4+123的和 */
    public static int print4(int n){
        if(n == 0){
            return 0;
        }
      return print4(n/10) + n%10;

    }
    public static void main4(String[] args) {
        System.out.println(print4(1234));
    }
    /*按顺序打印一个数字的每一位(例如 1234 打印出 1 2 3 4)
    *首先，要得到每一位数字，%10后 /10
    * 终止条件：n会一直变小，当n等于0时
    *递归公式：n/10 ,得到每一位是 n%10*/
    public static void print3(int n){
        if(n == 0){
            return;
        }
        print3(n/10);
        System.out.print(n%10+" ");
    }
    public static void main3(String[] args) {
        print3(1234);
    }
    /*求n的阶乘
    * 终止条件：n = 1
    * 递归公式: n! = n*(n-1)!*/
    public static int print2(int n){
        if(n == 1){
            return 1;
        }else{
           return n * print2(n-1);
        }
    }
    public static void main2(String[] args) {
        System.out.println( print2(5));
    }
   /* 我给的数是3，用递归打印1-3的数字
   递归的终止条件：a = 1
   递归公式：每次减1，直到为1，然后就可以归了。
  */
    public static void print(int n){
        if(n == 1){
            System.out.println(n);
            return;
        }
        print(n-1);
        System.out.println(n);

    }

    public static void main1(String[] args) {
       print(3);
    }
}
